﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
// 原题连接：https://leetcode.cn/problems/find-k-closest-elements/
/*
题目描述：
给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）
的 k 个数。返回的结果必须要是按升序排好的。
整数 a 比整数 b 更接近 x 需要满足：

|a - x| < |b - x| 或者
|a - x| == |b - x| 且 a < b
 

示例 1：
输入：arr = [1,2,3,4,5], k = 4, x = 3
输出：[1,2,3,4]

示例 2：
输入：arr = [1,2,3,4,5], k = 4, x = -1
输出：[1,2,3,4]
 

提示：
1 <= k <= arr.length
1 <= arr.length <= 104
arr 按 升序 排列
-104 <= arr[i], x <= 104
*/


// 开始解题：
// 方法2——二分法+双指针
 // 先写一个二分查找法,返回从右向左第一个小于target的元素的下标
int binary_search(int* nums, int left, int right, int target) {
    assert(nums);
    int mid = 0;
    while (left < right) {
        if (nums[right] < target) {
            return right;
        }
        mid = left + (right - left) / 2;
        if (nums[mid] >= target) {
            right = mid - 1;
        }
        else {
            left = mid;
        }
    }
    return left;
}
int* findClosestElements(int* arr, int arrSize, int k, int x, int* returnSize) {
    assert(arr && returnSize);
    int left = binary_search(arr, 0, arrSize - 1, x);
    int right = left + 1;

    int* answer = (int*)malloc(k * sizeof(int));
    if (NULL == answer) {
        perror("malloc fail");
        return NULL;
    }
    *returnSize = k;
    while (k--) {
        if (left < 0) {
            right++;
        }
        else if (right >= arrSize) {
            left--;
        }
        else if (x - arr[left] <= arr[right] - x) {
            left--;
        }
        else {
            right++;
        }
    }
    // 拷贝数据到答案数组
    memcpy(answer, arr + left + 1, (right - left - 1) * sizeof(int));
    return answer;
}



int main() {
    int nums[] = { 0,0,1,2,3,3,4,7,7,8 };
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int k = 3;
    int x = 5;
    int returnSize = 0;
    int* answer = findClosestElements(nums, numsSize, k, x, &returnSize);
    int i = 0;
    for (i = 0; i < returnSize; i++) {
        printf("%d ", answer[i]);
    }

    return 0;
}